package Test0406;

import java.util.Arrays;

public class mergeSort {
    public static void merge(int[] test,int[] temp, int begin, int mid, int end){

        int p1 = begin, p2 = mid + 1, t = begin;
        while(p1 <= mid && p2 <= end){
            if(test[p1]<= test[p2])
                temp[t++] = test[p1++];
            else
                temp[t++] = test[p2++];
        }
        while(p1 <= mid) temp[t++] = test[p1++];
        while(p2 <= end) temp[t++] = test[p2++];
        for(int i = begin;i <= end;i++){
            test[i] = temp[i];
        }
    }
    public static void merge_sort(int[] test,int[] temp, int begin, int end)
    {
        if(begin< end){
            int mid = (begin + end) / 2;
            merge_sort(test,temp,begin,mid);
            merge_sort(test,temp,mid + 1,end);
            merge(test,temp,begin,mid,end);
        }
    }

    public static void main(String[] args) {
        int[] test = new int[]{1,3,8,7,4,2,9,6,5,10,12,11,0,15,14};
        System.out.println(Arrays.toString(test));
        int[] temp = new int[test.length];
        merge_sort(test,temp,0,test.length-1);
        System.out.println(Arrays.toString(test));
    }
}
